package com.agile.leetcode.easy.removeZeroSumSublists;


import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
 * <p>
 * 删除完毕后，请你返回最终结果链表的头节点。
 * <p>
 * <p>
 * <p>
 * 你可以返回任何满足题目要求的答案。
 * <p>
 * （注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）
 * <p>
 * 示例 1：
 * <p>
 * 输入：head = [1,2,-3,3,1]
 * 输出：[3,1]
 * 提示：答案 [1,2,1] 也是正确的。
 * <p>
 * 示例 2：
 * <p>
 * 输入：head = [1,2,3,-3,4]
 * 输出：[1,2,4]
 * <p>
 * 示例 3：
 * <p>
 * 输入：head = [1,2,3,-3,-2]
 * 输出：[1]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author KD
 * @Date 2021/3/1 15:05
 */
public class RemoveZeroSumSublist {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(3);
        node2.next = node1;
        ListNode node3 = new ListNode(-3);
        node3.next = node2;
        ListNode node4 = new ListNode(2);
        node4.next = node3;
        ListNode node5 = new ListNode(1);
        node5.next = node4;
        RemoveZeroSumSublist removeZeroSumSublist = new RemoveZeroSumSublist();
        ListNode node = removeZeroSumSublist.removeZeroSumSublists(node5);
        System.out.println(node);
    }

    public ListNode removeZeroSumSublists(ListNode head) {
        // 创建哑结点
        ListNode dummy = new ListNode(0);
        // 将哑结点连接
        dummy.next = head;
        // 创建hashMap
        Map<Integer, ListNode> map = new HashMap<>(10);
        // 循环
        // 定义sum
        int sum = 0;
        for (ListNode node = dummy; node != null; node = node.next) {
            sum += node.val;
            // 放入map，如果有有为0的会字节覆盖
            map.put(sum, node);
        }
        sum = 0;
        // 再次循环
        for (ListNode node = dummy; node != null; node = node.next) {
            sum += node.val;
            node.next = map.get(sum).next;
        }
        return dummy.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    public ListNode(int x) {
        this.val = x;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
